// https://leetcode.cn/problems/add-binary/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        string ans = "";
        int carray = 0;
        int len_a = a.size(), len_b = b.size();
        int len = max(len_a, len_b);

        for (int i = 0; i < len; i++) {
            int num_a = i >= len_a ? 0 : a[i] - '0';
            int num_b = i >= len_b ? 0 : b[i] - '0';
            int sum = num_a + num_b + carray;
            carray = sum / 2;
            ans.push_back('0' + sum % 2);
        }
        if (carray) {
            ans.push_back('0' + carray);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};